package main

import (
	"fmt"
	"strings"
)

var exists = make(map[int]int) //斐波拉契数列字典dict

var exists1 = make(map[int]int) //n阶数列乘积字典dict

func add(a, b int) int {
	return a + b
}

func main() {
	//顺序表，链表，hash表优劣
	//在规模很小的情况下，这三者的效率都很高。随着规模的增加，这三种数据结构的特性会出现明显差异。
	//在规模较大的前提下：
	//顺序表：相当于在内存中分配一串连续的空间，这个空间分割成一定数量的单元供顺序表中的元素来使用，其中存在先后顺序。
	//		在尾部追加/删除效率很高O(1)，频繁在尾部追加/删除的前提下推荐使用。但是在头部/中间添加元素效率低下。因为会需要在内存中移动/赋值添加位置后后面的元素，随着规模增大，会对效率影响越来越大。
	//		使用索引获取顺序表中索引对应的元素，效率很高。否则需要遍历顺序表，效率随规模下降。修改元素和获取元素的效率一致。
	//链表：链表不需要在内存中分配连续的空间然后分割来存储每个元素。链表的每个元素分散在内存的各处，同样存在先后顺序，他们的先后关系通过该元素的头指针和尾指针来确定。
	//		在链表的任何位置插入/删除数据的效率都比较高效。
	//		在头部插入新元素时，前头部元素断开头指针（单向/双向指针）后，头指针指向新元素，新元素指向前头元素，即可完成插入。
	//		在头部删除元素时，删除元素断开头指针和第二元素的指针（单向/双向指针）后，头指针指向前第二元素，即可完成删除。
	//		在中间插入新元素时，插入位置元素断开前一个元素指针和后一个元素的指针（单向/双向指针）后，前一个元素指针指向新元素，新元素指向后一个元素，即可完成插入。
	//		在中间删除元素时，删除断开元素前一个元素指针和后一个元素的指针（单向/双向指针）后，前一个元素指针指向后一个元素元素，即可完成删除。
	//		在尾部插入新元素时，前尾部元素断结尾指针（单向/双向指针）后，前尾部元素指向新元素，新元素指向尾指针，即可完成插入。
	//		在尾部删除元素时，删除元素断开尾指针和倒数第二元素的指针（单向/双向指针）后，倒数第二元素指向尾指针，即可完成删除。
	//		使用索引获取链表中索引对应的元素，通过先后指针获取对应索引位置的元素效率很高。否则需要遍历链表，效率随规模下降。修改元素和获取元素的效率一致。
	//hash表：hash表保存的key-value键值对的数据。其中的key是关键。
	//		在插入时，先对key进行hash运算，获取保存数据的地址，使用拉链法在该地址中保存指向保存value数据的链表指针。value内存保存在该链表中。
	//		在删除时，同样先对Key进行hash运算，获取保存数据的地址，从该地址的链表指针获取对应的链表，查找/获取相应的value并进行删除。
	//		在获取/修改key对应的值value时，同样需要先对key进项hash运算，获取保存数据的地址，在该地址指向的链表中获取/修改数据即可。
	//这三种数据结构的curd存在的不同，使他们可以使用在不同的场景向下。但是，如果遍历/根据值查找索引/key，在规模交大的前提下效率都会非常低下。

	//函数调用过程描述
	c := add(1, 2)
	fmt.Println(c)
	//函数调用的过程：（以执行到打印c为结束）
	//运行golang的main入口函数，编译并开始运行该程序的一个进程
	//通过编译，函数会保存在该进程所占内存的堆/代码段中
	//然后首先向栈中压入main函数栈帧，其中包括参数c int
	//然后再栈中压入add函数栈帧，其中包括参数（1,2），然后调用堆/代码段中的add函数体对数据进行处理，并将结果赋值给main栈帧的参数c中
	//随着add函数体执行的结束，add函数栈帧消亡
	//打印开始，向栈中压入fmt.Println函数栈帧
	//fmt.Println函数栈帧中从main栈帧中获取参数c，执行打印操作
	//打印操作完成后，fmt.Println函数栈帧消亡
	//所有函数执行完成后，main函数栈帧消亡，该进程的运行流程完成

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

	fmt.Printf("循环n阶乘积结果：%d\n", seqv1(11))

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

	fmt.Printf("递归n阶乘积结果：%d\n", seqv2(11))

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

	fmt.Printf("循环变递归n阶乘积结果：%d\n", seqv3(11, 1, 2))

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

	fmt.Printf("优化递归n阶乘积结果：%d\n", seqv2p(11))

	fmt.Printf("优化版递归n阶乘积字典结果：%v\n", exists1)

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

	fmt.Printf("循环斐波拉契数字结果：%d\n", fib1(30))

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

	fmt.Printf("循环转递归斐波拉契数字结果：%d\n", fib1v2(30, 1, 1))

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

	fmt.Printf("递归斐波拉契数字结果：%d\n", fib1v1(30))

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

	fmt.Printf("优化版递归斐波拉契数字结果：%d\n", fib1v1p(30))

	fmt.Printf("优化版递归斐波拉契数组字典结果：%v\n", exists)

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")

	fmt.Printf("正三角输出结果为:\r\n%s\n", triangles(12))

	fmt.Println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")
}

// n阶乘积的循环写法
func seqv1(n int) int {
	switch {
	case n <= 0:
		return 0
	case n == 1:
		return 1
	}
	mul, next := 1, 2        //初始化n阶计算的参数
	for i := 1; i < n; i++ { //使用循环来进行n阶乘积
		mul = mul * next
		next++ //乘积后一个参数自增
	}
	return mul
}

// n阶乘积的递归写法
func seqv2(n int) int {
	switch {
	case n <= 0:
		return 0
	case n == 1:
		return 1
	default:
		return seqv2(n-1) * n //先求得n-1阶的结果再计算n阶
	}

}

// n阶乘积的循环变递归写法
func seqv3(n, mul, next int) int {
	switch {
	case n <= 0:
		return 0
	case n == 1:
		return mul
	}
	mul, next = mul*next, next+1 //从头开始计算并修改形参
	return seqv3(n-1, mul, next) //使用递归计算下一阶乘积
}

// n阶乘积的递归优化写法，使用dict保存重复计算数据
func seqv2p(n int) int {
	switch {
	case n <= 0:
		return 0
	case n == 1:
		return 1
	default:
		mul, ok := exists1[n-1] //使用dict保存可能存在的重复计算
		if !ok {
			mul = seqv2p(n - 1)
			exists1[n-1] = mul
		}
		return mul * n
	}
}

// 打印正三角形
func triangles(n int) string {
	if n == 0 {
		return ""
	}
	builder := new(strings.Builder) //使用字符串构建器
	//字符串你换构建器也可以使用：builder := new(bytes.Buffer)
	//builder.WriteRune(9)
	//builder.WriteByte(0x41)
	//builder.Write([]byte{0x61, 0x62, 0x63, 0x64})

	for i := 1; i <= n; i++ {
		for j := n; j > 0; j-- {
			tmp := fmt.Sprintf("%d", j) //获取每行需要打印的字符串
			if j <= i {
				builder.WriteString(tmp)
			} else {
				builder.WriteString(strings.ReplaceAll(tmp, tmp, strings.Repeat(" ", len(tmp)))) //当i>j时，将字符串中的字符替换为空格/其他标识符
			}
			if j > 1 {
				builder.WriteString(strings.Repeat(" ", 2)) //每个输出之间增加空格/其他标识符间隔
			}
		}
		builder.WriteString("\r\n") //每行输出完成后换行回车
	}
	return builder.String() //输出字符串
}

// 斐波拉契数列的循环写法
func fib1(n int) int {
	switch {
	case n <= 0:
		return 0
	case n < 3:
		return 1
	}
	a, b := 1, 1
	for i := 0; i < n-2; i++ {
		a, b = b, a+b
	}
	return b
}

// 斐波拉契数列的递归写法
func fib1v1(n int) int {
	switch {
	case n <= 0:
		return 0
	case n <= 2:
		return 1
	}
	return fib1v1(n-1) + fib1v1(n-2)
}

// 斐波拉契数列的循环变递归的写法
func fib1v2(n, a, b int) int {
	switch {
	case n <= 0:
		return 0
	case n <= 2:
		return b
	}
	a, b = b, a+b
	return fib1v2(n-1, a, b)
}

// 斐波拉契数列的递归优化写法，记录下每次递归的结果
func fib1v1p(n int) int {
	switch {
	case n <= 0:
		return 0
	case n <= 2:
		return 1
	}
	start, ok := exists[n-1] //查询字典减少不必要的重复计算
	if !ok {
		exists[n-1] = fib1v1p(n - 1)
		start = exists[n-1]
	}

	end, ok1 := exists[n-2] //查询字典减少不必要的重复计算
	if !ok1 {
		exists[n-2] = fib1v1p(n - 2)
		end = exists[n-2]
	}
	return start + end
}

// 批改意见
// 1. 多种实现方法都很不错
// 2. 0的阶乘是1，负数没有阶乘，应该抛出异常，或给出提示